/**
 * 数独求解算法 (JavaScript实现)
 * 性能优化版本
 */

/**
 * 检查在给定位置放置数字是否有效
 */
function isValid(board, row, col, num) {
    // 检查行
    for (let x = 0; x < 9; x++) {
        if (board[row][x] === num) {
            return false;
        }
    }

    // 检查列
    for (let x = 0; x < 9; x++) {
        if (board[x][col] === num) {
            return false;
        }
    }

    // 检查3x3子网格
    let startRow = row - row % 3;
    let startCol = col - col % 3;
    for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
            if (board[i + startRow][j + startCol] === num) {
                return false;
            }
        }
    }

    return true;
}

/**
 * 找到下一个空单元格
 */
function findEmptyCell(board) {
    for (let row = 0; row < 9; row++) {
        for (let col = 0; col < 9; col++) {
            if (board[row][col] === 0 || board[row][col] === '') {
                return [row, col];
            }
        }
    }
    return null;
}

/**
 * 使用回溯算法解决数独 - 优化版本
 */
function solveSudokuAlgorithm(board) {
    const emptyCell = findEmptyCell(board);
    if (!emptyCell) {
        return true; // 没有空单元格，解决完成
    }
    
    const [row, col] = emptyCell;
    
    // 按照"最少可能值"启发式排序数字尝试顺序
    const possibleNumbers = getPossibleNumbers(board, row, col);
    
    for (let num of possibleNumbers) {
        board[row][col] = num;
        
        // 递归求解
        if (solveSudokuAlgorithm(board)) {
            return true;
        }
        
        // 回溯
        board[row][col] = 0;
    }
    
    return false;
}

/**
 * 获取指定位置可能的数字列表
 */
function getPossibleNumbers(board, row, col) {
    const possible = [];
    
    for (let num = 1; num <= 9; num++) {
        if (isValid(board, row, col, num)) {
            possible.push(num);
        }
    }
    
    return possible;
}

/**
 * 查找所有可能的解
 */
function findAllSolutions(board) {
    const solutions = [];
    const boardCopy = JSON.parse(JSON.stringify(board)); // 创建副本以避免修改原数组
    
    function findSolutions(currentBoard) {
        const emptyCell = findEmptyCell(currentBoard);
        if (!emptyCell) {
            // 找到一个解，将其添加到解列表中
            solutions.push(JSON.parse(JSON.stringify(currentBoard)));
            return solutions.length >= 2; // 最多找两个解以检查唯一性
        }
        
        const [row, col] = emptyCell;
        
        // 按照"最少可能值"启发式排序数字尝试顺序
        const possibleNumbers = getPossibleNumbers(currentBoard, row, col);
        
        for (let num of possibleNumbers) {
            currentBoard[row][col] = num;
            
            // 递归查找解
            if (findSolutions(currentBoard)) {
                // 如果已找到足够多的解，提前返回
                return true;
            }
            
            // 回溯
            currentBoard[row][col] = 0;
        }
        
        return false;
    }
    
    findSolutions(boardCopy);
    return solutions;
}

/**
 * 检查数独是否有唯一解
 */
function hasUniqueSolution(board) {
    const solutions = findAllSolutions(board);
    return solutions.length === 1;
}

/**
 * 逐步求解数独，返回求解步骤
 */
function solveSudokuStepByStepAlgorithm(board) {
    const steps = [];
    const boardCopy = JSON.parse(JSON.stringify(board)); // 创建副本以避免修改原数组
    
    function solveWithSteps(currentBoard, stepList) {
        const emptyCell = findEmptyCell(currentBoard);
        if (!emptyCell) {
            return true; // 没有空单元格，解决完成
        }
        
        const [row, col] = emptyCell;
        
        // 按照"最少可能值"启发式排序数字尝试顺序
        const possibleNumbers = getPossibleNumbers(currentBoard, row, col);
        
        for (let num of possibleNumbers) {
            // 记录步骤
            stepList.push({
                row: row,
                col: col,
                num: num,
                action: 'try'
            });
            
            currentBoard[row][col] = num;
            
            // 递归求解
            if (solveWithSteps(currentBoard, stepList)) {
                return true;
            }
            
            // 回溯，记录步骤
            stepList.push({
                row: row,
                col: col,
                num: 0,
                action: 'backtrack'
            });
            
            currentBoard[row][col] = 0;
        }
        
        return false;
    }
    
    solveWithSteps(boardCopy, steps);
    return steps;
}

/**
 * 检查数独是否有效（用于错误检查）
 */
function isValidSudoku(board) {
    // 检查每一行
    for (let row = 0; row < 9; row++) {
        const rowSet = new Set();
        for (let col = 0; col < 9; col++) {
            const num = board[row][col];
            if (num !== 0 && num !== '') {
                if (rowSet.has(num)) {
                    return false;
                }
                rowSet.add(num);
            }
        }
    }
    
    // 检查每一列
    for (let col = 0; col < 9; col++) {
        const colSet = new Set();
        for (let row = 0; row < 9; row++) {
            const num = board[row][col];
            if (num !== 0 && num !== '') {
                if (colSet.has(num)) {
                    return false;
                }
                colSet.add(num);
            }
        }
    }
    
    // 检查每个3x3子网格
    for (let boxRow = 0; boxRow < 3; boxRow++) {
        for (let boxCol = 0; boxCol < 3; boxCol++) {
            const boxSet = new Set();
            for (let row = 0; row < 3; row++) {
                for (let col = 0; col < 3; col++) {
                    const num = board[boxRow * 3 + row][boxCol * 3 + col];
                    if (num !== 0 && num !== '') {
                        if (boxSet.has(num)) {
                            return false;
                        }
                        boxSet.add(num);
                    }
                }
            }
        }
    }
    
    return true;
}

/**
 * 查找数独中的错误
 */
function findSudokuErrors(board) {
    const errors = [];
    
    // 检查每一行
    for (let row = 0; row < 9; row++) {
        const rowMap = new Map();
        for (let col = 0; col < 9; col++) {
            const num = board[row][col];
            if (num !== 0 && num !== '') {
                if (rowMap.has(num)) {
                    // 找到重复数字
                    const prevCol = rowMap.get(num);
                    errors.push({ row: row, col: col, type: 'row' });
                    errors.push({ row: row, col: prevCol, type: 'row' });
                } else {
                    rowMap.set(num, col);
                }
            }
        }
    }
    
    // 检查每一列
    for (let col = 0; col < 9; col++) {
        const colMap = new Map();
        for (let row = 0; row < 9; row++) {
            const num = board[row][col];
            if (num !== 0 && num !== '') {
                if (colMap.has(num)) {
                    // 找到重复数字
                    const prevRow = colMap.get(num);
                    errors.push({ row: row, col: col, type: 'col' });
                    errors.push({ row: prevRow, col: col, type: 'col' });
                } else {
                    colMap.set(num, row);
                }
            }
        }
    }
    
    // 检查每个3x3子网格
    for (let boxRow = 0; boxRow < 3; boxRow++) {
        for (let boxCol = 0; boxCol < 3; boxCol++) {
            const boxMap = new Map();
            for (let row = 0; row < 3; row++) {
                for (let col = 0; col < 3; col++) {
                    const actualRow = boxRow * 3 + row;
                    const actualCol = boxCol * 3 + col;
                    const num = board[actualRow][actualCol];
                    if (num !== 0 && num !== '') {
                        if (boxMap.has(num)) {
                            // 找到重复数字
                            const [prevRow, prevCol] = boxMap.get(num);
                            errors.push({ row: actualRow, col: actualCol, type: 'box' });
                            errors.push({ row: prevRow, col: prevCol, type: 'box' });
                        } else {
                            boxMap.set(num, [actualRow, actualCol]);
                        }
                    }
                }
            }
        }
    }
    
    return errors;
}

/**
 * 评估数独难度
 */
function evaluateDifficulty(board) {
    // 简单的难度评估基于空单元格数量
    let emptyCells = 0;
    for (let row = 0; row < 9; row++) {
        for (let col = 0; col < 9; col++) {
            if (board[row][col] === 0 || board[row][col] === '') {
                emptyCells++;
            }
        }
    }
    
    if (emptyCells < 30) return "简单";
    if (emptyCells < 50) return "中等";
    return "困难";
}